package com.hy;

import java.util.Arrays;
import java.util.Random;

/**
 * Created With IntelliJ IDEA.
 * Descriptions: 堆排序
 * author: Mr.Du
 * Date: 2022/11/6
 * Time: 22:08
 */
public class HeapSort {
    
    public static void main(String[] args) {
        HeapSort hSort = new HeapSort();
        int[] nums = new int[10];
        Random r = new Random();
        // 跑五次
        for(int i = 0;i < 5;i++){
            for(int j = 0; j < nums.length;j++){
                nums[j] = r.nextInt(1000);
            }
            System.out.println("原数组: ");
            System.out.println(Arrays.toString(nums));
            hSort.heapSort(nums);
            System.out.println("堆排序后的数组: ");
            System.out.println(Arrays.toString(nums));
        }
    }
    
    public void initBigHeap(int[] nums,int i,int len){
        int tmp = nums[i];//先取出当前元素i
        for(int k = i * 2 + 1; k < len; k = k * 2 + 1){
            //从i结点的左子结点开始，也就是2i+1处开始
            //先找到左右结点最大的那个
            if(k + 1 < len && nums[k] < nums[k+1]){
                //如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            //将最大子结点和父节点比较，
            //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            if(nums[k] > tmp){
                nums[i] = nums[k];
                //不交换的原因是：要在当前结点的所有孩子结点中，找出比当前结点值大的结点
                //用i记录当前最小值的位置
                i = k;
            }else{
                break;
            }
        }
        nums[i] = tmp;//将temp值放到最终的位置
    }
    
    public void heapSort(int[] nums){
        int len = nums.length;
        for(int i = len / 2;i >= 0;i--){
            initBigHeap(nums,i,len);
        }
    
        //边输出堆顶边调整
        for (int j = len - 1; j > 0; j--) {
            //将堆顶元素与末尾元素进行交换
            swap(nums, 0, j);
            //重新对堆进行调整
            initBigHeap(nums, 0, j);
        
        }
    }
    
    public void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
